package com.offer;

import com.study.common.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: leetcode 35
 * @author: jzhou
 * @date: 2022-12-05 16:19
 * @version: 1.0
 * @description: 复杂链表的复制
 **/
public class CopyNode {
    public Node copyList(Node head) {
        Node curr = head;
        Node virtual = new Node(0),pre = virtual;
        while (curr != null){
            Node node = new Node(curr.val);  // 复制节点 cur
            pre.next = node;                 // 新链表的 前驱节点 指向 当前节点

            curr = curr.next;                // 遍历下一节点
            pre = node;                      // 保存当前新节点
        }

        return virtual.next;
    }


    // 引入额外的 hash 表
    public Node copyRandomList(Node head) {

        Node curr = head;
        Map<Node,Node> map = new HashMap<>();
        while (curr != null){
            map.put(curr,new Node(curr.val));
            curr = curr.next;
        }

        //构建 next 和 random 指针
        curr = head;
        while (curr != null){
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }

    //拼接 + 拆分
    public Node copyRandomList1(Node head) {
        if (head == null) return null;
        Node curr = head;
        // 1. 复制各节点，并构建拼接链表
        while (curr != null){
            Node tmp = new Node(curr.val + 1);
            tmp.next = curr.next;
            curr.next = tmp;
            curr = tmp.next;
        }
//        // 2. 构建各新节点的 random 指向  curr.next.random = curr.random
        curr = head;
        while (curr != null){
            if (curr.random != null){
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        // 3. 拆分两链表

        Node res = head.next,pre = head;
        curr = head.next;
        while (curr.next != null){
            pre.next = pre.next.next;
            curr.next = curr.next.next;
            pre = pre.next;
            curr = curr.next;
        }
        pre.next = null; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }

    public static void main(String[] args) {
        CopyNode cn = new CopyNode();
        Node n1 = new Node(1);
        Node n3 = new Node(3);
        Node n5 = new Node(5);
        Node n7 = new Node(7);
        Node n9 = new Node(9);
        n1.next = n3;
        n3.next = n5;
        n5.next = n7;
        n7.next = n9;
        cn.copyRandomList1(n1);

    }

}
